1. Field of the Invention
This invention relates to techniques for converting representations of digital circuits, such as logic diagrams or schematics, into layouts for circuit implementation, and more specifically to the identification of logic input equivalences for controlling and optimizing circuit area and circuit delays during the layout process.
2. Description of the Prior Art
Many very sophisticated logic synthesis and layout tools have been developed for producing circuit layouts from circuit and logic diagrams. One recent article, xe2x80x9cEffective Coupling between Logic Synthesis and Layout Tools for Synthesis of Area and Speed-Efficient Circuitsxe2x80x9d, Chandrasekhar, McCharles and Wallace, published in VLSI DESIGN, 1997, Vol. 5, No. 2, pp. 125-140, co-authored by the inventor hereof, proposes coupling between logic synthesis and layout tools to improve post-layout circuit implementation.
As noted in that article, many circuits produced by synthesis or other methods contain internal nodes at the outputs of logic gates that implement the same logic function and are therefore logically equivalent. Such nodes are considered output equivalent and techniques are provided for exploiting output equivalents during the layout of digital circuits. Similarly, input equivalence is demonstrated in logic circuits in which the output of an output gate does not change even if the circuit configuration is changed by interchanging the drivers connected to input gates feeding that output gate, as shown in FIG. 8 of that article.
Although techniques are provided for working with output equivalence, what are needed are techniques for identifying and exploiting input equivalences in the synthesis and layout of digital logic circuits.
The present invention provides improved techniques for identifying input equivalence in digital circuits for use, for example, in swapping pins in order to modify circuit layout. These techniques include the steps of decomposing the circuit into one or more regions, then decomposing the logic function of each region into a directed graph of logic functions, and using the directed graph, identifying pin swap groups and swapping pins as desired for final layout or configuration.
In one embodiment, the present invention decomposes the circuit into fanout free regions (FFRs), and the logic function of each fanout free region is decomposed by generating quasi canonical models for the cells of the circuit. Then, a swap structure is created using these models to form the directed graph, to facilitate identification of input equivalences. The present invention proceeds by looking for extensible symmetric logic functions (such as AND, OR and XOR functions) within and between gates in a logic circuit. Such functions are grown backwards as long as they can continue to be extended and then analyzed to identify input equivalences to identify permutable pins.
In another embodiment, the circuit is decomposed into coalesced regions, where each member of a group of coalesced regions has at most fan out to only one other region. The decomposition of the logic functions of the coalesced regions are accomplished by constructing binary decision diagrams (BDD) for outputs of these regions, and then using the corresponding BDD to construct a ds-prime decomposition for each of the logic function, forming the directed graph. These BDDs are then used to associate nets in the original circuit with the arcs of the directed graph, and compared to identify input equivalences.
The present invention may be conveniently implemented in a computer by coding appropriate software on computer coded media or by any other conventional means of programming a computer. The required software may be written by a person of ordinary skill in the art of developing programs for analyzing digital circuits for layout and similar operations.
These and other features and advantages of this invention will become further apparent from the detailed description and accompanying figures that follow. In the figures and description, numerals indicate the various features of the invention, like numerals referring to like features throughout both the drawings and the description.